package eashrine;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @Author: Siantar
 * @Date: 2023-07-18-12:02
 * @Description: 1.0
 */
public class T1851 {
    public int[] minInterval(int[][] intervals, int[] queries) {
        int[] res = new int[queries.length];
        Integer[] queriesIndex = new Integer[queries.length];
        for (int i = 0; i < queries.length; i++) {
            queriesIndex[i] = i;
        }
        Arrays.sort(queriesIndex, (i, j) -> queries[i] - queries[j]);
        Arrays.sort(intervals, (i, j) -> i[0] - j[0]);
        Arrays.fill(res, -1);
        PriorityQueue<int[]> pq = new PriorityQueue<>((i, j) -> i[0] - j[0]);
        int i = 0;
        for (int index : queriesIndex) {
            while (i < intervals.length && intervals[i][0] <= queries[index]) {
                pq.offer(new int[]{intervals[i][1] - intervals[i][0] + 1, intervals[i][0], intervals[i][1]});
                i++;
            }
            while (!pq.isEmpty() && pq.peek()[2] < queries[index]) {
                pq.poll();
            }
            if (!pq.isEmpty()) {
                res[index] = pq.peek()[0];
            }
        }
        return res;
    }
}
